import java.util.ArrayList;
import java.util.List;

public class Solution {
    //爬楼梯
    public int climbStairs(int n) {
        int[] dp = new int[n+1];
        if(n == 1) {
            return 1;
        }
        if(n == 2) {
            return 2;
        }
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for(int i = 4; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
    //三角形最小路径和
    public static int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        //dp[i][j]代表到达i，j位置时的最小距离
        int[][] dp = new int[n+1][n+1];
        //将dp表全部初始化为无穷大
        for(int i = 0; i < n+1; i++) {
            for(int j = 0; j < n+1; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        dp[1][1] = triangle.get(0).get(0);
        for(int i = 2; i < n+1; i++) {
            for(int j = 1; j <= i; j++) {
                dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j-1])+triangle.get(i-1).get(j-1);
            }
        }
        int min = Integer.MAX_VALUE;
        for(int i = 0; i <= n; i++) {
            if(dp[n][i] < min)
                min = dp[n][i];
        }
        return min;
    }

    public static void main(String[] args) {
        List<List<Integer>> triangle = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();
        cur.add(2);
        List<Integer> cur1 = new ArrayList<>();
        cur1.add(3);
        cur1.add(4);
        List<Integer> cur2 = new ArrayList<>(2);
        cur2.add(6);
        cur2.add(5);
        cur2.add(7);
        List<Integer> cur3 = new ArrayList<>();
        cur3.add(4);
        cur3.add(1);
        cur3.add(8);
        cur3.add(3);
        triangle.add(cur);
        triangle.add(cur1);
        triangle.add(cur2);
        minimumTotal(triangle);
    }
}
